package com.剑指offer.no24;

import java.util.*;


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tmpCurrentNode = head;
        ListNode tmpNextNode = head.next;
        ListNode tmpPreNode = null;
        return head;

    }
}


class Solution01 {

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //把链表节点全部摘掉放到栈中
        Stack<ListNode> nodeStack = new Stack<>();

        while (head != null) {
            nodeStack.push(head);
            head = head.next;
        }

        //栈中的结点全部出栈，然后重新连成一个新的链表
        ListNode headNode = nodeStack.pop();
        ListNode tmpCurrentNode = headNode;
        while (!nodeStack.isEmpty()){
            tmpCurrentNode.next = nodeStack.pop();
            tmpCurrentNode = tmpCurrentNode.next;
        }
        tmpCurrentNode.next =null;
        return headNode;
    }
}



class Solution02 {

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 新链表
        ListNode newHead = null;

        while (head!= null){
            ListNode tmpNode = head.next;
            head.next = newHead;
            newHead = head;
            head = tmpNode;
        }
        return newHead;
    }
}


class Solution03 {

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tmpCurNode = null;
        ListNode tmpNextNode = head;
        while(tmpNextNode != null){

            ListNode tmpNode = tmpNextNode.next;
            tmpNextNode.next = tmpCurNode;

            // 两个指针往后移
            tmpCurNode = tmpNextNode;

            tmpNextNode = tmpNode;
        }
        return tmpCurNode;
    }
}

